package hash.medium;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 砖墙
 * 输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
 * 输出：2
 * 示例 2：
 *
 * 输入：wall = [[1],[1],[1]]
 * 输出：3
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/brick-wall
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class BrickWall_554 {

    public int leastBricks(List<List<Integer>> wall) {
        //= == == =
        //=== = ==
        //= === ==
        //== ====
        //=== = ==
        //= === = =
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0, sum = 0; i < wall.size(); i++, sum = 0) {
            List<Integer> integers = wall.get(i);
            for (Integer integer : integers) {
                sum += integer;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
            map.remove(sum);
        }
        int size = wall.size();
        int min = size;
        for (Integer integer : map.keySet()) {
            min = Math.min(min, size - map.get(integer));
        }
        return min;
    }
}
